package com.study.algorithm.linkedList;

import java.util.HashMap;
import java.util.Map;

public class CopyRandomList {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // 哈希表存储原节点到新节点的映射
        Map<Node, Node> map = new HashMap<>();

        // 第一次遍历：创建所有新节点并建立映射
        Node current = head;
        while (current != null) {
            map.put(current, new Node(current.val));
            current = current.next;
        }

        // 第二次遍历：设置新节点的next和random指针
        current = head;
        while (current != null) {
            Node newNode = map.get(current);
            // 设置next指针
            if (current.next != null) {
                newNode.next = map.get(current.next);
            }
            // 设置random指针
            if (current.random != null) {
                newNode.random = map.get(current.random);
            }
            current = current.next;
        }

        // 返回新链表的头节点
        return map.get(head);
    }
}
